package algorithm
{
	import datastructure.Edge;
	import datastructure.Graph;
	import datastructure.Vertex;

	/**
	 * Prim算法 
	 * @author juxuan
	 * 
	 */	
	public class Prim
	{
		private var mst:Array;	//组成图的最小生成树的边的集合
		private var versMST:Array;	//最小生成树的顶点集合
		
		private var graph:Graph;
		private var startVert:Vertex;
		private var vertNotMSt:Array;
		
		public function Prim(g:Graph,start:Vertex,originVerArray:Array)
		{
			this.mst = new Array();
			this.versMST = new Array();
			this.startVert = start;
			this.startVert.isStart = true;
			this.versMST.push(this.startVert);
			this.graph = g;
			this.initVertNotInMST(originVerArray);
		}
		
		/**
		 * 运行Prim算法 
		 * 
		 */		
		public function run():void
		{
			for(var i:int = 1; i < this.graph.verNum(); i++)
			{
				if(this.vertNotMSt.length == 0)
					return;
				var vert:Vertex = this.vertNotMSt.shift();
				var edge:Edge = new Edge(vert.closestVer,vert,vert.closestDist);
				this.mst.push(edge);
				this.versMST.push(vert);
				reset();
			}
		}
		
		
		public function getVersMST():Array
		{
			return this.versMST;
		}
		
		public function geTMST():Array
		{
			return this.mst;
		}
		
		/**
		 * 初始化不再当前树的顶点
		 * @param originVerArray
		 * 
		 */		
		private function initVertNotInMST(originVerArray:Array):void
		{
			this.vertNotMSt = new Array();
			for(var i:int = 0; i < originVerArray.length; i++)
			{
				if(originVerArray[i].index != startVert.index)
				{
					var vertex:Vertex = originVerArray[i] as Vertex;
					var weight:int = this.graph.weight(this.startVert.index,vertex.index);
					if(weight != 0)
					{
						vertex.closestVer = this.startVert;
						vertex.closestDist = weight;
					}
					this.vertNotMSt.push(vertex);
				}
			}
			this.vertNotMSt.sortOn("closestDist",Array.NUMERIC);	//按closestDist从小到大排序
		}
		
		/**
		 * 当一个新的顶点加入树后,对剩下的不在树中的顶点进行处理 
		 * 
		 */		
		private function reset():void
		{
			for(var i:int = 0;i < this.vertNotMSt.length; i++)
			{
				for(var j:int = 0;j < this.versMST.length;j++)
				{
					var weight:int = this.graph.weight(this.vertNotMSt[i].index,this.versMST[j].index);
					if(weight < this.vertNotMSt[i].closestDist && weight!= 0)
					{
						this.vertNotMSt[i].closestDist = weight;
						this.vertNotMSt[i].closestVer = this.versMST[j];
					}
				}
			}
			
			this.vertNotMSt.sortOn("closestDist",Array.NUMERIC);
		}
		
		
	}
}